package lfu

import (
	algo "SpringCache/cachealgorithm"
	"container/heap"
	"math/rand"
	"time"
)

var DefaultMaxBytes int64 = 100
var DefaultExpireRandom time.Duration = 3 * time.Minute

type NowFunc func() time.Time

var nowFunc NowFunc = time.Now

// Cache 定义LFU缓存结构体
type Cache struct {
	maxBytes  int64                         // 允许使用的最大内存
	nbytes    int64                         // 当前已经使用的内存
	pq        PriorityQueue                 // 优先队列，用于LFU算法
	cache     map[string]*Item              // 实际保存键值的缓存
	OnEvicted func(key string, value Value) // 当节点被删除时可以选择性调用回调函数

	// Now is the Now() function the cache will use to determine
	// the current time which is used to calculate expired values
	// Defaults to time.Now()
	Now NowFunc
	//
	ExpireRandom time.Duration
}

// Item 定义优先队列中的元素
type Item struct {
	key     string
	value   Value
	expire  time.Time // 过期时间
	addTime time.Time
	count   int // 访问次数
	index   int // 优先队列中的索引
}

// PriorityQueue 实现优先队列
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	// 首先比较访问次数，次数少的优先
	if pq[i].count != pq[j].count {
		return pq[i].count < pq[j].count
	}
	// 访问次数相同，比较添加时间，添加早的优先
	return pq[i].addTime.Before(pq[j].addTime)
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // 避免内存泄漏
	item.index = -1 // 表示已移除
	*pq = old[0 : n-1]
	return item
}

type Value = algo.Value

// New 创建一个新的LFU缓存实例
func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
	if maxBytes > DefaultMaxBytes {
		return &Cache{
			maxBytes:     DefaultMaxBytes,
			pq:           make(PriorityQueue, 0),
			cache:        make(map[string]*Item),
			OnEvicted:    onEvicted,
			Now:          nowFunc,
			ExpireRandom: DefaultExpireRandom,
		}
	}
	return &Cache{
		maxBytes:     maxBytes,
		pq:           make(PriorityQueue, 0),
		cache:        make(map[string]*Item),
		OnEvicted:    onEvicted,
		Now:          nowFunc,
		ExpireRandom: DefaultExpireRandom,
	}
}

// Len 返回缓存中元素的数量
func (c *Cache) Len() int {
	return len(c.pq)
}

// Get 获取缓存中的元素
func (c *Cache) Get(key string) (value Value, ok bool) {
	if item, ok := c.cache[key]; ok {
		// 如果item过期了，将它们移除缓存
		if item.expire.Before(c.Now()) {
			c.removeItem(item)
			return nil, false
		}
		// 增加访问次数
		item.count++
		// 调整优先队列
		heap.Fix(&c.pq, item.index)
		return item.value, true
	}
	return nil, false
}

// RemoveOldest 移除最不经常使用的元素
func (c *Cache) RemoveOldest() {
	if len(c.pq) > 0 {
		item := heap.Pop(&c.pq).(*Item)
		delete(c.cache, item.key)
		c.nbytes -= int64(len(item.key)) + int64(item.value.Len())
		if c.OnEvicted != nil {
			c.OnEvicted(item.key, item.value)
		}
	}
}

// Remove 移除指定key的元素
func (c *Cache) Remove(key string) {
	if item, ok := c.cache[key]; ok {
		c.removeItem(item)
	}
}

// removeItem 移除指定的item
func (c *Cache) removeItem(item *Item) {
	heap.Remove(&c.pq, item.index)
	delete(c.cache, item.key)
	c.nbytes -= int64(len(item.key)) + int64(item.value.Len())
	if c.OnEvicted != nil {
		c.OnEvicted(item.key, item.value)
	}
}

// Add 添加元素到缓存中
func (c *Cache) Add(key string, value Value, expire time.Time) {
	// randDuration 是用户添加的过期时间进行一定范围的随机，用于防止大量缓存同一时间过期而发生缓存雪崩
	randDuration := time.Duration(rand.Int63n(int64(c.ExpireRandom)))

	if item, ok := c.cache[key]; ok {
		// 如果key已经存在则将value替换
		c.nbytes += int64(value.Len()) - int64(item.value.Len())
		item.value = value
		item.expire = expire.Add(randDuration)
		// 增加访问次数
		item.count++
		// 调整优先队列
		heap.Fix(&c.pq, item.index)
	} else {
		item := &Item{
			key:     key,
			value:   value,
			expire:  expire.Add(randDuration),
			addTime: c.Now(),
			count:   1,
		}
		heap.Push(&c.pq, item)
		c.cache[key] = item
		c.nbytes += int64(len(key)) + int64(value.Len())
	}
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOldest()
	}
}
